// 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树
// 思路1，递归
function sortedArrayToBST(nums) {
    if (!nums.length) {
        return null
    }
    let midIndex = Math.floor(nums.length / 2)
    let midVal = nums[midIndex]
    let root = new TreeNode(midVal)
    root.left = sortedArrayToBST(nums.slice(0, midIndex))
    root.right = sortedArrayToBST(nums.slice(midIndex + 1))
    return root
}

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

// 思路2，迭代
function sortedArrayToBST2(nums) {
    if (!nums.length) {
        return null
    }
    let root = new TreeNode(0)
    let numsQueue = [nums]
    let nodeQueue = [root]
    while (nodeQueue.length) {
        let curNode = nodeQueue.shift()
        let curNums = numsQueue.shift()
        let midIndex = Math.floor(curNums.length / 2)
        let midVal = curNums[midIndex]
        curNode.val = midVal
        let leftNums = curNums.slice(0, midIndex)
        let rightNums = curNums.slice(midIndex + 1)
        if (leftNums.length) {
            let leftNode = new TreeNode(0)
            curNode.left = leftNode
            numsQueue.push(leftNums)
            nodeQueue.push(leftNode)
        }
        if (rightNums.length) {
            let rightNode = new TreeNode(0)
            curNode.right = rightNode
            numsQueue.push(rightNums)
            nodeQueue.push(rightNode)
        }
    }
    return root
}


let arr = [-10, -3, 0, 5, 9]
console.log(sortedArrayToBST(arr))
console.log(sortedArrayToBST2(arr))